package lanqiao;
/**
 * 完全背包
 * 有N种物品和一个容量为V 的背包，每种物品都有无限件可用。
 * 放入第i种物品的费用是Ci，价值是Wi。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。
 * 输入：
 *     3 8
 *     2 3
 *     3 6
 *     4 7
 * 输出：
 *     15
 */
import java.util.Scanner;
public class ADV_144_2 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // 物品种类数
        int m = input.nextInt(); // 背包能装重量

        int[] weight = new int[n+1]; //物品的重量
        int[] val = new int[n+1]; //物品的价值
        for(int i=1; i<=n; i++) {
            weight[i] = input.nextInt(); //第i个物品的重量
            val[i] = input.nextInt(); //第i个物品的价值
        }

        //dp[i][j]表示前i个物品放入容量为j的背包的最大价值
        int[][] dp = new int[n+1][m+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                //不选第i个物品的情况
                dp[i][j] = dp[i-1][j];
                //选择第i个物品的情况
                if(j >= weight[i]){
                    //此时就不像0-1背包一样，转换为dp[i-1][j-weight[i]]+val[i]
                    //而是转换为dp[i][j-weight[i]] + val[i]，因为选了一个物品i后，还可以再选它，所以还是从前i个物品中选
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-weight[i]] + val[i]);
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}